# -*- coding: utf-8 -*-
"""Controlador de Afns"""

import random

from lex import model
from lex.controllers.pila_cola import Pila, Cola
from lex.lib.base import BaseController
from lex.model import metadata, DBSession
from lex.model.model import AnalizadorLexico, ExpresionRegular, Afn
import pydot
from pylons.i18n import ugettext as _, lazy_ugettext as l_
from sqlalchemy import func
from sqlalchemy.exc import IntegrityError, SQLAlchemyError
from tg import expose, flash, require, url, request, redirect, tmpl_context, \
    validate
import transaction
from webhelpers import paginate

import networkx as nx
from repoze.what import predicates
from tgext.admin.controller import AdminController, AdminConfig
from tgext.admin.tgadminconfig import TGAdminConfig


# import matplotlib.pyplot as plt
precedencia = {
              "*" : 10,
              "+" : 10,
              "?" : 10,
              "." : 9,
              "|" : 8,
              "(" :-1,
              ")" :-1,
              }

__all__ = ['AfnsController']

class AfnsController(BaseController):

    @expose('lex.templates.afns.generar_afns')
    def generar_afn(self, id_analizador_lexico, page=1):
        """Metodo para generar el AFN del analizador seleccionado"""
        try:

################################################################################
# Advertencia: Este proceso tambien se realiza en la funcion "generar_afd" del
# "afds_controlador.py". Asi que, cualquier cambio realizado aqui, tambien debe 
# considerarse si se realiza o no en la funcion "generar_afd".
#################CONSTRUCCION DEL AFN POR EL METODO DE THOMPSON#################

            # INICIALIZACION DE VARIBLES
            # Inicializamos algunas variables necesarias.
            analizador_lexico = DBSession.query(AnalizadorLexico).get(id_analizador_lexico)
            nombre_analizador = analizador_lexico.nombre_analizador_lexico
            lista_alfabetos = analizador_lexico.alfabetos
            lista_expresiones = analizador_lexico.expresiones_regulares
            mi_alfabeto = []
            lista_de_tupla_nombre_definicion = []
            lista_final_definicion_expresiones = []
            mi_diccionario_alfa = {}
            mi_diccionario_expr = {}
            mi_diccionario_operadores = {"(":"(", ")":")", "*":"*", "+":"+", "?":"?", ".":".", "|":"|"}

            # OBTENCION DEL ALFABETO Y CREACION DE SU DICCIONARIO:
            # Agrupamos todos los alfabetos del analizador lexico correspondiente,
            # eliminamos los elementos duplicados y "creamos un diccionario" con
            # la lista resultante.
            if lista_alfabetos != []:
               for alfabeto in lista_alfabetos:
                   definicion_alfabeto = alfabeto.definicion_alfabeto
                   lista_simbolos = definicion_alfabeto.split()
                   for c in lista_simbolos:
                       mi_alfabeto.append(c)  # Agrupacion de alfabetos.

               mi_alfabeto = list(set(mi_alfabeto))  # Eliminacion de duplicados.
               mi_diccionario_alfa = dict.fromkeys(mi_alfabeto)  # Creacion del diccionario.
            else:
               flash(_("Su analizador lexico no dispone de Alfabeto!"), 'error')
               redirect("/cadenas/analizadores_disponibles")

            # OBTENCION DE LOS NOMBRES Y DEFINICIONES DE LAS EXPRESIONES REGULARES, Y CREACION DE SU DICCIONARIO:
            # Creamos una lista con los nombres de las expresiones regulares.
            # Creamos una lista con las definiciones de las expresiones regulares.
            # "Creamos un diccionario" para las expresiones regulares, que tienen
            # por clave el nombre y por valor la definicion.
            if lista_expresiones != []:
               for expresion in lista_expresiones:
                   tupla_nombre_definicion = (expresion.nombre_expresion_regular, expresion.definicion_expresion_regular)
                   lista_de_tupla_nombre_definicion.append(tupla_nombre_definicion)
                   mi_diccionario_expr[expresion.nombre_expresion_regular] = expresion.definicion_expresion_regular  # Creacion del diccionario.
            else:
               flash(_("Su analizador lexico no dispone de Expresiones Regulares!"), 'error')
               redirect("/cadenas/analizadores_disponibles")

            # En cada definicion de expresion regular, sustituimos cualquier
            # otra definicion que forme parte de esa definicion.
            if lista_de_tupla_nombre_definicion != []:
               for tupla_nombre_definicion in lista_de_tupla_nombre_definicion:
                   nombre_expresion = tupla_nombre_definicion[0]
                   definicion_expresion = tupla_nombre_definicion[1]
                   # En este "while" se buscan definiciones que se encuentran
                   # dentro de "definicion_expresion".
                   i = 0
                   while i < len(definicion_expresion):
                         c = definicion_expresion[i]
                         # En este "if" se verifica si se trata de operadores.
                         # De ser asi se continua el ciclo en la posicion siguiente.
                         if mi_diccionario_operadores.has_key(c):
                            i = i + 1
                         # En este "else" se extrae la definicion.
                         else:
                            simbolo_o_palabra = c
                            j = i + 1
                            ban = False
                            # Aqui se trata de formar la definicion encontrada.
                            if j < len(definicion_expresion):
                               while not mi_diccionario_operadores.has_key(definicion_expresion[j]):
                                     simbolo_o_palabra = simbolo_o_palabra + definicion_expresion[j]
                                     ban = True
                                     i = i + 1
                                     j = i + 1
                                     if j < len(definicion_expresion):
                                        pass
                                     else:
                                        break

                            # Se verifica que la definicion encontrada exista.
                            # Deberia existir si llega hasta aqui. De este modo se
                            # la inserta dentro de "definicion_expresion", y la busqueda
                            # se retrocede hasta la posicion donde comienza la sustitucion.
                            if ban == True:
                               if mi_diccionario_expr.has_key(simbolo_o_palabra) and simbolo_o_palabra != nombre_expresion:
                                  pos_inicial = i - len(simbolo_o_palabra) + 1
                                  pos_final = i + 1
                                  definicion_expresion = definicion_expresion[0:pos_inicial] + "(" + mi_diccionario_expr.get(simbolo_o_palabra) + ")" + definicion_expresion[pos_final:]
                                  i = pos_inicial - 1
                               else:
                                  if simbolo_o_palabra == nombre_expresion:
                                     flash(_("Se han detectado definiciones que provocan ciclos!"), 'error')
                                     redirect("/cadenas/analizadores_disponibles")
                                  else:
                                     flash(_("Existe una definicion de expresion no valida!"), 'error')
                                     redirect("/cadenas/analizadores_disponibles")

                            i = i + 1
                   
                   t = (nombre_expresion, definicion_expresion)
                   lista_final_definicion_expresiones.append(t)

               # Eliminamos los duplicados de la lista final de las definiciones de las 
               # expresiones regulares, luego ordenamos la lista.
               # lista_final_definicion_expresiones = list(set(lista_final_definicion_expresiones))
               # lista_final_definicion_expresiones.sort()
            else:
               flash(_("Su analizador lexico no dispone de definiciones de Expresiones Regulares!"), 'error')
               redirect("/cadenas/analizadores_disponibles")


            # CONSTRUCCION DEL AFN POR EL METODO DE THOMPSON:
            numeracion_estados = 1
            tabla_transiciones = {}
            lista_i_f_por_definicion = []
            estado_inicio_aceptacion = []

            # Utilizamos la lista que contiene las expresiones regulares.
            if lista_final_definicion_expresiones != []:
               for tupla_nombre_definicion in lista_final_definicion_expresiones:
                   nombre_expresion = tupla_nombre_definicion[0]
                   definicion_expresion = tupla_nombre_definicion[1]

                   # Cada definicion transformamos a su representacion posfija.
                   definicion_posfija = infijo_a_posfijo(definicion_expresion, precedencia)

                   # Utilizamos una pila para ir construyendo la tabla de transiciones.
                   pila = Pila()
                   for c in definicion_posfija:

                       if mi_diccionario_alfa.has_key(c):
                          pila.push(c)
                       elif mi_diccionario_operadores.has_key(c):

                          # Thompson para un caracter con el operador "*".
                          if c == "*":
                             s = pila.top() 
                             pila.pop()
                             if mi_diccionario_alfa.has_key(s):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s, n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("", n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("", n1)
                                lista_transiciones = tabla_transiciones[n2]
                                lista_transiciones.append(t)
                                          
                                inicio_actual = n3
                                fin_actual = n4
                                t = (inicio_actual, fin_actual)
                                pila.push(t)
                             else:
                                n1 = s[0]
                                n2 = s[1]
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("", n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("", n1)
                                lista_transiciones = tabla_transiciones[n2]
                                lista_transiciones.append(t)

                                inicio_actual = n3
                                fin_actual = n4
                                t = (inicio_actual, fin_actual)
                                pila.push(t)

                          # Thompson para un caracter con el operador "+".
                          elif c == "+":
                             s = pila.top() 
                             pila.pop()
                             if mi_diccionario_alfa.has_key(s):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s, n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("", n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("", n1)
                                lista_transiciones = tabla_transiciones[n2]
                                lista_transiciones.append(t)

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s, n3)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n5] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n4
                                t = (inicio_actual, fin_actual)
                                pila.push(t)
                             else:
                                n1 = s[0]
                                n2 = s[1]
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1

                                # Copiamos la transicion que va de n1 a n2 para concatenar luego,
                                # ya que a+=aa*, entonces necesitamos tener una replica de a.
                                # Primero, cargamos los nodos a recorrer.
                                pila_recorrido = Pila()
                                pila_recorrido.push(n1)
                                lista_de_nodos = []
                                while not pila_recorrido.empty():
                                      nodo = pila_recorrido.top()
                                      lista_de_nodos.append(nodo)
                                      pila_recorrido.pop()
                                      lista_nodo = tabla_transiciones[nodo]
                                      for t in lista_nodo:
                                          dest = t[1]
                                          if dest != n2:
                                             pila_recorrido.push(dest)

                                # Establecemos la nueva numeracion.
                                nueva_numeracion = {}
                                nueva_numeracion[n1] = n5
                                nueva_numeracion[n2] = n3
                                for nodo in lista_de_nodos:
                                    if nodo == n1:
                                       pass
                                    else:
                                       n = numeracion_estados
                                       numeracion_estados = numeracion_estados + 1
                                       nueva_numeracion[nodo] = n

                                # Empezamos el copiado.
                                for nodo in lista_de_nodos:
                                    lista_nodo = tabla_transiciones[nodo]
                                    lista_transiciones = []
                                    for t in lista_nodo:
                                        s = t[0]
                                        dest = t[1]
                                        nt = (s, nueva_numeracion[dest])
                                        lista_transiciones.append(nt)
                                    tabla_transiciones[nueva_numeracion[nodo]] = lista_transiciones
                                        
                                # Se unen todas las piezas.
                                t = ("", n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("", n1)
                                lista_transiciones = tabla_transiciones[n2]
                                lista_transiciones.append(t)

                                inicio_actual = n5
                                fin_actual = n4
                                t = (inicio_actual, fin_actual)
                                pila.push(t)

                          # Thompson para un caracter con el operador "?".
                          elif c == "?":
                             s = pila.top() 
                             pila.pop()
                             if mi_diccionario_alfa.has_key(s):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s, n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("", n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("", n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("", n5)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("", n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n6] = lista_transiciones

                                inicio_actual = n3
                                fin_actual = n4
                                t = (inicio_actual, fin_actual)
                                pila.push(t)
                             else:
                                n1 = s[0]
                                n2 = s[1]
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("", n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("", n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("", n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("", n5)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("", n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n6] = lista_transiciones

                                inicio_actual = n3
                                fin_actual = n4
                                t = (inicio_actual, fin_actual)
                                pila.push(t)

                          # Thompson para un caracter con el operador ".".
                          elif c == ".":
                             s2 = pila.top()
                             pila.pop()
                             s1 = pila.top()
                             pila.pop()                                
                             if mi_diccionario_alfa.has_key(s1) and mi_diccionario_alfa.has_key(s2):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s2, n3)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                t = (s1, n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                inicio_actual = n1
                                fin_actual = n3
                                t = (inicio_actual, fin_actual)
                                pila.push(t)
                             elif mi_diccionario_alfa.has_key(s1) and mi_diccionario_alfa.has_key(s2) == False:
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = s2[0]
                                n3 = s2[1]
                                t = (s1, n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                inicio_actual = n1
                                fin_actual = n3
                                t = (inicio_actual, fin_actual)
                                pila.push(t)
                             elif mi_diccionario_alfa.has_key(s1) == False and mi_diccionario_alfa.has_key(s2):
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n1 = s1[0]
                                n2 = s1[1]
                                t = (s2, n3)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                inicio_actual = n1
                                fin_actual = n3
                                t = (inicio_actual, fin_actual)
                                pila.push(t)

                             elif mi_diccionario_alfa.has_key(s1) == False and mi_diccionario_alfa.has_key(s2) == False:
                                n1 = s1[0]
                                n2 = s1[1]
                                n3 = s2[0]
                                n4 = s2[1]

                                lista_transiciones = tabla_transiciones[n3]
                                tabla_transiciones[n2] = lista_transiciones
                                tabla_transiciones.pop(n3)

                                inicio_actual = n1
                                fin_actual = n4
                                t = (inicio_actual, fin_actual)
                                pila.push(t)

                          # Thompson para un caracter con el operador "|".
                          elif c == "|":
                             s2 = pila.top()
                             pila.pop()
                             s1 = pila.top()
                             pila.pop()                  
                             if mi_diccionario_alfa.has_key(s1) and mi_diccionario_alfa.has_key(s2):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s1, n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones
                                t = (s2, n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t1 = ("", n1)
                                t2 = ("", n3)
                                lista_transiciones = []
                                lista_transiciones.append(t1)
                                lista_transiciones.append(t2)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("", n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n4] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n6
                                t = (inicio_actual, fin_actual)
                                pila.push(t)
                             elif mi_diccionario_alfa.has_key(s1) and mi_diccionario_alfa.has_key(s2) == False:
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n3 = s2[0]
                                n4 = s2[1]
                                t = (s1, n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t1 = ("", n1)
                                t2 = ("", n3)
                                lista_transiciones = []
                                lista_transiciones.append(t1)
                                lista_transiciones.append(t2)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("", n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n4] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n6
                                t = (inicio_actual, fin_actual)
                                pila.push(t)
                             elif mi_diccionario_alfa.has_key(s1) == False and mi_diccionario_alfa.has_key(s2):
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n1 = s1[0]
                                n2 = s1[1]
                                t = (s2, n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t1 = ("", n1)
                                t2 = ("", n3)
                                lista_transiciones = []
                                lista_transiciones.append(t1)
                                lista_transiciones.append(t2)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("", n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n4] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n6
                                t = (inicio_actual, fin_actual)
                                pila.push(t)

                             elif mi_diccionario_alfa.has_key(s1) == False and mi_diccionario_alfa.has_key(s2) == False:
                                n1 = s1[0]
                                n2 = s1[1]
                                n3 = s2[0]
                                n4 = s2[1]

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t1 = ("", n1)
                                t2 = ("", n3)
                                lista_transiciones = []
                                lista_transiciones.append(t1)
                                lista_transiciones.append(t2)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("", n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n4] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n6
                                t = (inicio_actual, fin_actual)
                                pila.push(t)
                                  
                   t = pila.top()
                   pila.pop()
                   # Verificar si se trata de un solo caracter o no el que quedo en la pila.
                   if mi_diccionario_alfa.has_key(t):
                      n1 = numeracion_estados
                      numeracion_estados = numeracion_estados + 1
                      n2 = numeracion_estados
                      numeracion_estados = numeracion_estados + 1
                      tt = (t, n2)
                      lista_transiciones = []
                      lista_transiciones.append(tt)
                      tabla_transiciones[n1] = lista_transiciones

                      inicio_actual = n1
                      fin_actual = n2
                      tt = (inicio_actual, fin_actual)
                      lista_i_f_por_definicion.append(tt)
                   else:
                      lista_i_f_por_definicion.append(t)


               # Unimos los automatas de cada definicion, para obtener un unico AFN.
               if lista_i_f_por_definicion != [] and len(lista_i_f_por_definicion) > 1:
                  pila = Pila()           
                  for t_i_f in lista_i_f_por_definicion:
                      pila.push(t_i_f)
                      if pila.size() < 2:
                         pass
                      else:
                         t2 = pila.top()
                         pila.pop()
                         t1 = pila.top()
                         pila.pop()
                         n1 = t1[0]
                         n2 = t1[1]
                         n3 = t2[0]
                         n4 = t2[1]

                         n5 = numeracion_estados
                         numeracion_estados = numeracion_estados + 1
                         n6 = numeracion_estados
                         numeracion_estados = numeracion_estados + 1
                         t1 = ("", n1)
                         t2 = ("", n3)
                         lista_transiciones = []
                         lista_transiciones.append(t1)
                         lista_transiciones.append(t2)
                         tabla_transiciones[n5] = lista_transiciones

                         t = ("", n6)
                         lista_transiciones = []
                         lista_transiciones.append(t)
                         tabla_transiciones[n2] = lista_transiciones
                         lista_transiciones = []
                         lista_transiciones.append(t)
                         tabla_transiciones[n4] = lista_transiciones

                         inicio_actual = n5
                         fin_actual = n6
                         t = (inicio_actual, fin_actual)
                         pila.push(t)
                  
                  t = pila.top()
                  pila.pop()
                  estado_inicio_aceptacion.append(t)

               elif len(lista_i_f_por_definicion) == 1:
                  t = lista_i_f_por_definicion[0]
                  estado_inicio_aceptacion.append(t)
               else:
                  flash(_("No se pudo obtener los estados de inicio y de aceptacion! SQLAlchemyError..."), 'error')
                  redirect("/cadenas/analizadores_disponibles")

################################################################################
#######################PROCESO DE DIBUJO DEL GRAFO DIRIGIDO#####################

            # Generamos los grafos para el Afn resultante.
            G = pydot.Dot(graph_type='digraph')
            claves = tabla_transiciones.keys()

            # El nodo de inicio coloreamos en rojo, el de aceptacion en verde.
            t = estado_inicio_aceptacion[0]
            inicio = t[0]
            aceptacion = t[1]
            G.add_node(pydot.Node(str(inicio), shape="circle", style="filled", fillcolor="red", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='black'))
            G.add_node(pydot.Node(str(aceptacion), shape="circle", style="filled", fillcolor="green", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='black'))

            # #Creamos los demas nodos.
            if claves != []:
               for clave in claves:
                   if clave != inicio and clave != aceptacion:
                      G.add_node(pydot.Node(str(clave), shape="circle", style="filled", fillcolor="white", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='black'))
            else:
               flash(_("No se pudo obtener las claves de la Tabla de Transiciones!"), 'error')
               redirect("/cadenas/analizadores_disponibles")
               
##########################################################################
            i = 1
            nueva = []
            aux = []
            while i <= len(tabla_transiciones):
                print("Infinitoooooooooooooooooooooooooooooooo")
                if(len(tabla_transiciones[i]) == 1):
                    for h in tabla_transiciones[i]:
                        aux.append(i)
                        if h[0] == "":
                            aux.append("Vacio")
                        else:
                            aux.append(h[0])
                        aux.append(h[1])    
                        nueva.append(aux)            
                else:
                    for h in tabla_transiciones[i]:
                        aux.append(i)
                        if h[0] == "":
                            aux.append("Vacio")
                        else:
                            aux.append(h[0])
                        aux.append(h[1])
                        nueva.append(aux)
                        aux = []    

                i = i + 1
                aux = []

##########################################################################
            # Creamos las aristas.
            tuplas_clave_valor = tabla_transiciones.items()
            if tuplas_clave_valor != []:
               for tupla_clave_valor in tuplas_clave_valor:
                   n1 = tupla_clave_valor[0]
                   aristas = tupla_clave_valor[1]
                   if aristas != []:
                      for arista in aristas:
                          c = arista[0]
                          n2 = arista[1]
                          if c == "":
                             transicion = "ε"
                          else:
                             transicion = c
                          G.add_edge(pydot.Edge(str(n1), str(n2), label=str(transicion), fontcolor='blue', fontsize="15.0", color="black"))
                   else:
                      pass

            # Dibujamos el grafo y lo guardamos como imagen.
            G.write_png("/home/rodolfo/tpcompiladores/LEX/lex/public/images/afn_graph.png")

################################################################################

        except SQLAlchemyError:
            flash(_("No se pudo acceder a Generar Afn! SQLAlchemyError..."), 'error')
            redirect("/cadenas/analizadores_disponibles")
        except (AttributeError, NameError):
            flash(_("No se pudo acceder a Generar Afn! Hay Problemas con el servidor..."), 'error')
            redirect("/cadenas/analizadores_disponibles")

        return dict(id_analizador_lexico=id_analizador_lexico, nombre_analizador=nombre_analizador,
                    lista_final_definicion_expresiones=lista_final_definicion_expresiones, inicio=inicio, aceptacion=aceptacion,nueva=nueva)


#----------- Funcion que convierte una expresion infija en otra posfija---------

def infijo_a_posfijo(expr, precedencia):

    pila = Pila()
    cola = Cola()
    
    for c in expr:
        if c not in precedencia:
            cola.enqueue(c)
        elif c == ")":
            while not pila.empty():
                if pila.top() == "(":
                    pila.pop()
                    break
                else:
                    cola.enqueue(pila.top())
                    pila.pop()
        else:
            if pila.empty() or c == "(":
                pila.push(c)
            else:
                while not pila.empty() and precedencia[c] <= precedencia[pila.top()]:
                    cola.enqueue(pila.top())
                    pila.pop()
                pila.push(c)
    
    while not pila.empty():
        cola.enqueue(pila.top())
        pila.pop()

    return list(cola)

"""

            #Generamos los grafos para el Afn resultante.
            G = nx.DiGraph()
            G.colores = {}
            claves = tabla_transiciones.keys()

            #El nodo de inicio coloreamos en rojo, el de aceptacion en verde.
            t = estado_inicio_aceptacion[0]
            inicio = t[0]
            aceptacion = t[1]
            G.add_node(inicio)
            G.add_node(aceptacion)
            G.colores[inicio] = 'red'
            G.colores[aceptacion] = 'green'

            ##Creamos los demas nodos.
            if claves != []:
               for clave in claves:
                   if clave != inicio and clave != aceptacion:
                      G.add_node(clave)
                      G.colores[clave] = 'coral'
            else:
               flash(_("No se pudo obtener las claves de la Tabla de Transiciones!"), 'error')
               redirect("/cadenas/analizadores_disponibles")
               
            #Creamos las aristas.
            tuplas_clave_valor = tabla_transiciones.items()
            if tuplas_clave_valor != []:
               for tupla_clave_valor in tuplas_clave_valor:
                   n1 = tupla_clave_valor[0]
                   aristas = tupla_clave_valor[1]
                   if aristas != []:
                      for arista in aristas:
                          c = arista[0]
                          n2 = arista[1]
                          G.add_edge(n1, n2, weight=int(1))
                   else:
                      pass

            #Dibujamos el grafo y lo guardamos como imagen.
            plt.clf()
            nx.draw_circular(G, node_color = [G.colores[v] for v in G], node_size=500)
            plt.savefig("../LEX/lex/public/images/afn_graph.png")
"""
